import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
class Solution1{

    /**
     * 三数之和
     * https://leetcode.cn/problems/3sum/
     */

    int l,r,c = 0;
    public List<List<Integer>> threeSum(int[] arr){
        //1,排序
        Arrays.sort(arr);
        List<List<Integer>> list = new ArrayList<>();


        //2.获取

        for(int i = 0;i <= arr.length - 3;i++){
            l = i + 1;
            r = arr.length - 1;
            if(list.size() != 0){
                if(list.get(c - 1).get(0) == arr[i]){
                    continue;
                }
            }
            //查找两个数
            while(l < r){

                ArrayList<Integer> ret = (ArrayList<Integer>) tow_num_sum(arr,0 - arr[i]);

                if(ret != null){

                        c++;
                        ret.add(0,arr[i]);
                        list.add(ret);
                        l++;
                        r--;
                }
                //去重
                while (l < r && (list.get(c -1).get(1) == arr[l])) {
                            l++;
                }
                while (l < r && (list.get(c - 1).get(2) == arr[r])) {
                            r--;
                }

            }
        }
        return list;
    }

    public  List<Integer> tow_num_sum(int[] arr,int target){

        while(l < r){
            if(arr[l] + arr[r] > target){
                r--;
            }else if(arr[l] + arr[r] < target){
                l++;
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(arr[l]);
                list.add(arr[r]);
                return list;
            }
        }
        return null;
    }

    public static void main(String[] args) {
//        int[] test = {1,1,1,2,2,2,3,3,3};
        //int[] test = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        int[] test = {1,-1,0,4};
        List<List<Integer>> ret = new ArrayList<>();

        Solution1 solution = new Solution1();
        List<List<Integer>> list = solution.threeSum(test);
        System.out.println("{" + list + "}");

    }
}
class Solution1_1 {

        public List<List<Integer>> threeSum(int[] nums) {

            List<List<Integer>> ret = new ArrayList<>();
            Arrays.sort(nums);
            int len = nums.length;
            for (int i = 0; i <= len - 3;) {
                if (nums[i] > 0)
                    return ret;

                int left = i + 1, right = len - 1, sum = 0;
                while (left < right) {

                    if (nums[i] + nums[left] + nums[right] > sum)
                        right--;
                    else if (nums[i] + nums[left] + nums[right] < sum)
                        left++;
                    else {
                        ret.add(new ArrayList(Arrays.asList(nums[i], nums[left], nums[right])));
                        left++;
                        right--;

                        //去重
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right + 1] == nums[right])
                            right--;
                    }
                }

                //去重i
                i++;
                while (i < len - 2) {
                    if (nums[i] == nums[i - 1])
                        i++;
                    else
                        break;
                }
            }
            return ret;

        }
    public static void main(String[] args) {
//        int[] test = {1,1,1,2,2,2,3,3,3};
        //int[] test = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        int[] test = {-1,0,1,2,-1,-4};

        Solution1_1 solution = new Solution1_1();
        List<List<Integer>> list = solution.threeSum(test);
        System.out.println("{" + list + "}");

    }
}

/**
 * 四个数之和
 * https://leetcode.cn/problems/4sum/
 */
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        //1.排序
        Arrays.sort(nums);

        List<List<Integer>> ret = new ArrayList<>();

        //2.固定两个数
        int length = nums.length;
        for(int i = 0;i < length - 3;){
            for(int j = i + 1;j < length - 2;){
                //定义左右双指针
                int left = j + 1,right = length  - 1;
                //遍历查找
                while(left < right){
                    //目标值可能用int存不下
                    long aim = (long)target - nums[i] - nums[j];
                    int sum = nums[left] + nums[right];
                    if(left < right && sum > aim){
                        right--;
                    }
                    else if(left < right && sum < aim ){
                        left++;
                    }else{
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));

                        //去重：left 与 right
                        while(left < right && nums[left] == nums[left -1]) left++;

                        while(left < right && nums[right + 1] == nums[right]) right--;
                    }
                }
                //去重j
                j++;
                while(j < length - 2 && nums[j] == nums[j - 1]) j++;
            }
            //去重i
            i++;
            while(i < length - 3 && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
    public static void main(String[] args) {
//        int[] test = {1,1,1,2,2,2,3,3,3};
        //int[] test = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        int[] test = {1,0,-1,0,-2,2};

        Solution solution = new Solution();
        List<List<Integer>> list = solution.fourSum(test,0);
        System.out.println("{" + list + "}");

    }
}

class Solution11 {
    public static int minSubArrayLen(int target, int[] nums) {

        //1.定义同向双指针
        int left=0,right,sum = 0,len = Integer.MAX_VALUE;
        for(right = 0;right < nums.length;right++){
            //2.进窗口
            sum += nums[right];
            while(sum >= target){
                //3.更新结果
                len = Math.min(len,right - left + 1);
                //4.出窗口
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    public static void main(String[] args) {



        System.out.println(Solution11.minSubArrayLen(7, new int[]{1,2,3,4,5}));
    }

}



